An essential semiconductor device is semiconductor memory, such as a random access memory (RAM) device. A RAM allows a memory circuit to execute both read and write operations on its memory cells. Typical examples of RAM devices include dynamic random access memory (DRAM) and static random access memory (SRAM).
Another form of memory is the content addressable memory (CAM) device. A conventional CAM is viewed as a static storage device constructed of modified RAM cells. A CAM is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers, gateways and switches, computer systems and other devices that require rapid content searching, such as routing data or tables for data networks or matching URLs. Some of these tables are “learned” from the data passing through the network. Other tables, however, are fixed tables that are loaded into the CAM by a system controller. These fixed tables reside in the CAM for a relatively long period of time. A word in a CAM is typically large and can be 96 bits or more.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., DRAM and SRAM). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address. In a CAM, however, data is stored in locations in a somewhat random fashion. The memory storage locations can be selected by an address bus, or the data can be written into the first empty memory storage location. Every memory storage location has a pair of status bits that keep track of whether the memory storage location is storing valid information or is empty and available for writing.
Once information is stored in a memory storage location, it is found by comparing every bit stored in memory storage location with data in the comparand register. When the contents stored in the CAM memory storage location do not match the data in the comparand register, the local match detection circuit returns a no match indication. When the contents stored in the CAM memory storage location match the data in the comparand register, the local match detection circuit returns a match indication. If one or more local match detect circuits return a match indication, the CAM device returns a “match” indication. Otherwise, the CAM device returns a “no-match” indication. In addition, the CAM may return the identification of the address/memory storage location in which the desired data is stored or one of such addresses, such as a highest priority match address, if more than one address contained matching data. Thus, with a CAM, the user supplies the data and gets back the address if there is a match found in memory.
Sometimes it is desirable to find a closest match if there are no exact matches between the words stored in the CAM array and the comparand word stored in the comparand register. In prior art CAMs, the search for the closest match, also referred to as the longest match in that a largest number of bits in a memory storage location match bits in the comparand word, is performed in one of two ways. In the first method, using binary CAMs, if a match is not found on the full comparand, then certain bits in the comparand are masked and the search operation is repeated in an attempt to find a match on less than all bits. If one bit of the comparand is masked at a time, then finding the closest possible match may require many repeated operations/searches.
In a second method, using ternary CAMs, data (e.g., such as routing data which may consist of, for example network addresses and/or URLs) in the CAM is not random but rather is stored in an ordered fashion. Data (a pattern) with the most complete information on the path to the destination are stored in locations with the highest priority. Routing data pertaining to a less important part of the path to the destination are stored in locations with a lower priority and bits in such words, that would otherwise carry information about the remainder of the routing path, are masked or set to the “don't care” state.
Using the second method would result in the longest match being located in a single operation because the word containing the larger number of bits that match bits in the comparand register has a higher priority and will, thus, be pointed to first. The second method has two major disadvantages, however. The second method requires the use of a ternary CAM. In a ternary CAM there are two bits in the CAM for each data bit, which almost doubles the size of the CAM. Secondly, multiple copies of the same data are stored in multiple locations with different levels of priority and more bits are masked in every copy of lower priority locations. Thus, it is desirable to have a CAM priority encoder capable of identifying the closest match to the comparand word without requiring extensive search durations and without requiring increased CAM sizes.